#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

/*
希尔排序
时间复杂度为:O(n*lgn)
空间复杂度为:O(1)
有无序序列：9 1 2 5 7 4 8 6 3 5
用一个递减序列进行分组，每组进行插入排序
递减序列通常可以为：n/2, n/4, ..., 1（n为数组长度）
故能够分组为：
第一轮分组：
[9，4],[1,8], [2,6],[5,3], [7,5]
将每一组进行插入排序后，得到：
[4,9],[1,8], [2,6],[3,5], [5,7]
第一轮排序后的结果：
4，1，2,3，5，9，8，6，5，7
第二轮分组：
[4,2,5,8,5],[1,3,9,6,7]s
第二轮排序后的结果：
2,1,4,3,5,6,5,7,8,9
第三趟分组：
[2,1,4,3,5,6,5,7,8,9]
第三趟排序后的结果：
1，2，3，4，5，5，6，7，8，9
*/
vector<int> shellSort(vector<int>& v)
{
    int grap = v.size()/2;
    //每隔grap个元素归为一组，每组进行插入排序
    while(grap>0)
    {
        for(int i=0;i<grap;i++)
        {
            //1 . . . . 2 . . . . 0 . . . . 3
            for(int j=i+grap;j<v.size();j+=grap)
            {  
                //寻找插入位置
                for(int c=j-grap;c>=0&&v[c]>v[j];c-=grap)
                {
                    swap(v[c],v[c+grap]);
                }
            }
        }
        cout<<"The "<<grap<<"th group is sorted"<<endl;
        for(int i=0;i<v.size();++i)
        {
            cout<<v[i]<<" ";
        }
        cout<<endl;
        grap/=2;
    }
    return v;
}
int main()
{
    cout<<"Enter the numbers:"<<endl;
    vector<int> v;
    int n;
    while(n!=-1)
    {
        cin>>n;
        v.push_back(n);
    }
    v.pop_back();
    v=shellSort(v);
    cout<<"The sorted vector is:"<<endl;
    for(int i=0;i<v.size();++i)
    {
        cout<<v[i]<<" ";
    }
    return 0;
}

